package com.since.algorithm.sort;

import java.util.Arrays;

/**
 * Created by Sincerity on 2020/5/14.
 * 描述：八大排序
 * 直接插入排序 {@link #insertSort(int[])}
 */
class InsertSort {
    public static void main(String[] args) {
        int[] array = {156, 495, 2, 16, -45, 982, 23};//
        System.out.println("原数组:" + Arrays.toString(array));
//        stepAnalysisInsertSort(array);
        insertSort(array);
    }

    /**
     * 插入排序
     *
     * @param array 目标数组
     */
    public static void insertSort(int[] array) {
        int insertVal; //需要插入的数字
        int insertIndex; //记录插入得位置
        for (int i = 1; i < array.length; i++) {
            //定义待插入的数
            insertVal = array[i];//2
            insertIndex = i - 1;//1
            //循环判断前一个位置的数是否大于待插入的数,并且用insertIndex记录需要插入的位置
            while (insertIndex >= 0 && array[insertIndex] > insertVal) {
                //array[2]=array[1]=495
                //array[1]=array[2]=495
                //array[0]=arr
                array[insertIndex + 1] = array[insertIndex];
                insertIndex--;
            }
            //得到需要插入的数的位置
            if (insertIndex + 1 != i) {
                System.out.println("--" + (insertIndex + 1));
                array[insertIndex + 1] = insertVal;
            }
//            if (insertIndex - 1 != i) {
//                array[insertIndex + 1] = insertVal;
//            }
//            while (insertIndex >= 0 && array[insertIndex] > insertVal) {
//                array[insertIndex + 1] = array[insertIndex];
//                insertIndex--;
//            }
//            if (insertIndex + 1 != i) {
//                array[insertIndex + 1] = insertVal;
//            }
            System.out.println("第" + i + "次排序后的数组:" + Arrays.toString(array));
        }
    }

    /**
     * 分步去图解插入排序
     *
     * @param array
     */
    private static void stepAnalysisInsertSort(int[] array) {
        //第一步: 对比数字为0 而比较的位置就是0+1位置
        // {156, 495, 2, 16, -45, 982, 23}==> {156(insertIndex), 495(insertVal), 2, 16, -45, 982, 23};
        int insertVal = array[1];
        int insertIndex = 1 - 1;
        for (int i = insertIndex; i >= 0; i--) {
            if (insertVal < array[i]) {
                array[insertIndex + 1] = array[insertIndex];
            }
        }
        array[insertIndex + 1] = insertVal;
        System.out.println("第二次排序后的数组:" + Arrays.toString(array));
        //第一步: 对比数字为0 而比较的位置就是0+1位置
        //[156, 495, 2, 16]==> [2, 156, 495, 16]
        int temp;
        for (int i = 2; i > 0; i--) {
            temp = array[i - 1];
            if (array[i] < array[i - 1]) {
                array[i - 1] = array[i];
                array[i] = temp;
            }

        }
        System.out.println("第二次排序后的数组:" + Arrays.toString(array));
    }
}
